#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N=1050;
const int M=10050;
const int INF=0x3f3f3f3f;
bool vis[N];
int pre[N],dis[N];
int cost[N][N];
int n,m;
int u,v,c;
int s,t;
int T;
void Dijkstra(){
    for(int i=0;i<n;i++){
        dis[i]=INF;
        vis[i]=false;
        pre[i]=-1;
    }
    dis[s]=0;
    for(int i=0;i<n;i++){
        //printf("%d\n",i);
        int k=-1;
        int Min=INF;
        for(int j=0;j<n;j++){
            if(!vis[j] && dis[j]<Min){
                Min=dis[j];
                k=j;
            }
        }
        if(k==-1){
            break;
        }
        //printf("%d\n",k);
        vis[k]=true;
        for(int j=0;j<n;j++){
            //这里！！！ 两点要有边才能更新
            if(!vis[j] && dis[j]>dis[k]+1 && cost[j][k]!=INF){
                //printf("%d %d\n",j,k);
                dis[j]=dis[k]+1;
                pre[j]=k;
            }
        }
    }
    // for(int i=0;i<n;i++){
    //     printf("%d ",dis[i]);
    // }
    // printf("\n");
}
int cnt;
int head[N],dep[N];
int cur[N];
struct Edge{
    int u,v,w,next;
}edge[M];
void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(cur,0,sizeof(cur));
}
void addEdge(int u,int v,int w){
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].u=v;
    edge[cnt].v=u;
    edge[cnt].w=0;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
bool bfs(){
    queue<int> q;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].v;
            int w=edge[i].w;
            if(w>0 && dep[v]==0){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    if(dep[t]==0){
        return false;
    }
    return true;
}
int dfs(int u,int flow){
    if(u==t){
        return flow;
    }
    for(int &i=cur[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        int w=edge[i].w;
        if(dep[v]==dep[u]+1 && w!=0){
            int dis=dfs(v,min(w,flow));
            if(dis>0){
                edge[i].w-=dis;
                edge[i^1].w+=dis;
                return dis;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        for(int i=0;i<n;i++){
            cur[i]=head[i];
        }
        while(int d=dfs(s,INF)){
            ans+=d;
        }
    }
    return ans;
}
int main(void){
    scanf("%d",&T);
    while(T--){
        memset(cost,0,sizeof(cost));
        init();
        scanf("%d%d",&n,&m);
        s=0,t=n-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cost[i][j]=i==j?0:INF;
            }
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&c);
            if(c<cost[u-1][v-1]){
                cost[u-1][v-1]=cost[v-1][u-1]=c;
            }
        }
        Dijkstra();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //printf("%d %d %d %d %d\n",i,j,cost[i][j],dis[i],dis[j]);
                if(cost[i][j]!=INF && i!=j && dis[j]==dis[i]+1){
                    //printf("%d %d\n",i,j);
                    addEdge(i,j,cost[i][j]);
                }
            }
        }
        // for(int i=0;i<cnt;i++){
        //     printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].w);
        // }
        int ans=dinic();
        printf("%d\n",ans);
    }
    return 0; 
}